package com.xiaoyu.stack;

import java.util.Stack;

/**
 * @program: DS_and_A
 * @description: 最小栈
 *设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
 *
 * push(x) —— 将元素 x 推入栈中。
 * pop()—— 删除栈顶的元素。
 * top()—— 获取栈顶元素。
 * getMin() —— 检索栈中的最小元素。
 *
 *
 *  Your MinStack object will be instantiated and called as such:
 *  MinStack obj = new MinStack();
 *  obj.push(val);
 *  obj.pop();
 *  int param_3 = obj.top();
 *  int param_4 = obj.getMin();
 *
 *
 * @author: YuWenYi
 * @create: 2021-05-07 08:29
 **/
/*
public class MinStack {

    private Integer[] elementData;

    private int top;

    //自己写法!
    */
/** initialize your data structure here. *//*

    public MinStack() {
        this.elementData = new Integer[16];
        this.top = -1;
    }

    public void push(int val) {
        if (this.elementData.length-1 == top){
            //扩容
            int oldCap = elementData.length;
            int newCap = oldCap + oldCap;
            elementData = Arrays.copyOf(elementData,newCap);
        }
        elementData[++top] = val;
    }

    public void pop() {
        if (top == -1){
            throw new ArrayIndexOutOfBoundsException("栈为空");
        }
        Integer item = elementData[top--];
        //System.out.println(item);
    }

    public int top() {
        if (top == -1){
            throw new ArrayIndexOutOfBoundsException("栈为空");
        }
        return elementData[top];
    }

    public int getMin() {
        if (top == -1){
            throw new ArrayIndexOutOfBoundsException("栈为空");
        }
        int temp = top;
        int min = elementData[temp--];
        while (temp >= 0){
            min = Math.min(min,elementData[temp]);
            temp--;
        }
        return min;
    }

    public static void main(String[] args) {
        MinStack minStack = new MinStack();
        minStack.push(-2);
        minStack.push(0);
        minStack.push(-3);
        System.out.println(minStack.getMin());
        minStack.pop();
        System.out.println(minStack.top());
        System.out.println("minStack.getMin() = " + minStack.getMin());

        //obj.pop();
*/
/*        int param_3 = obj.top();
        int param_4 = obj.getMin();
        System.out.println(param_3);
        System.out.println(param_4);*//*

    }

}
*/

//官方解答:辅助栈法,用栈实现栈..   如果不能使用辅助栈,那么需要每次入栈和出栈的时候维护一个最小值
class MinStack {
    private Stack<Integer> minStack;
    private Stack<Integer> helpStack;

    public MinStack() {
        minStack = new Stack<>();
        helpStack = new Stack<>();
        helpStack.push(Integer.MAX_VALUE);
    }

    public void push(int val) {
        minStack.push(val);
        helpStack.push(Math.min(helpStack.peek(),val));
    }

    public void pop() {
        minStack.pop();
        helpStack.pop();
    }

    public int top() {
       return minStack.peek();
    }

    public int getMin() {
        return helpStack.peek();
    }

    public static void main(String[] args) {
        MinStack minStack = new MinStack();
        minStack.push(-2);
        minStack.push(0);
        minStack.push(-3);
        System.out.println(minStack.getMin());
        minStack.pop();
        System.out.println(minStack.top());
        System.out.println("minStack.getMin() = " + minStack.getMin());
    }
}